package com.me.study.arithmeticAndDataStructure.arithmetic;

import java.util.Arrays;

/**
 * 字符串匹配的 KMP算法
 *
 * @author ME
 * @date   2019/7/9
 */
public class TestKMP {

    public static void main(String[] args) {
        TestKMP t = new TestKMP();
        System.out.println(Arrays.toString(t.getNext1("ababaaaba")));
    }

    public int[] getNext1(String str) {
        int[] intArr = new int[str.length() + 1];
        int j = 0;// 字符串的头字母
        int i = 1;// 字符串的尾字母
        intArr[1] = 0;
        while (i < str.length()) {
            if (j == 0 || str.charAt(j) == str.charAt(i)) {
                ++j;
                ++i;
                intArr[i] = j;
            } else {
                j = intArr[j];
            }
        }
        return intArr;
    }

    public int[] getNext2(String str) {
        int[] intArr = new int[str.length() + 1];
        int i = 0;// 字符串的头字母
        int j = 1;// 字符串的尾字母
        intArr[1] = 0;
        while (i < str.length()) {
            if (i == 0 || str.charAt(i) == str.charAt(j)) {
                ++i;
                ++j;
                intArr[j] = i;
            } else {
                ++j;
            }
        }
        return intArr;
    }
}
